1. Field of the Invention
The present invention provides a focus+context technique for visualizing large hierarchies; and more particularly provides for visualization of a hierarchy using a compressed half-plane model of hyperbolic geometry.
2. Description of Related Art
A focus+context technique for visualizing large hierarchies is described in U.S. Pat. No. 5,590,250, entitled “Layout of Node-link Structures in Space with Negative Curvature,” in U.S. Pat. No. 6,108,698, entitled “Node-Link Data Defining a Graph and a Tree Within the Graph,” and in U.S. Pat. No. 5,619,632, entitled “Displaying Node-link Structure with Region of Greater Spacings and Peripheral Branches.” Related prior art patent applications include: Local Relative Layout of Node-Link Structures in Space with Negative Curvature. John Lamping, Ramana Rao, Tichomir Tenev. EP Publication No. 0977155, 2 Feb. 2000. Mapping a Node-Link Structure to a Rendering Space Beginning from and Node. Ramana Rao, John Lamping, Tichomir Tenev. EP Publication No. 0977153, 2 Feb. 2000. Controlling Which Part of Data Defining a Node-Link Structure is in Memory. Tichomir Tenev, John Lamping, Ramana Rao. EP Publication No. 0977131, 2 Feb. 2000.
The prior art patents listed above, and the references cited in such publications, provide substantial background information about the state of the art, and reference is made to them for this purpose.
Prior art techniques described above can be understood by reference to FIG. 1. In the view of FIG. 1, a tree visualization consists of a node-link structure mapped into hyperbolic space and projected into a unit disc, resulting in a circular or elliptical view of the tree. By mapping the tree into hyperbolic space with a closed horizon defined by the unit disc, the entire tree is contained within an area that can be displayed all at once. The node-link structure in this example is an organization chart, with nodes for individuals in the organization. The mapping tends to focus on nodes in the center of the display, with nodes distant from the nodes in the center compressed into space approaching the rim in a manner that preserves some context about the position of the nodes in the center, relative to the rest of the hierarchy.
The original circle view is a pure focus+context visualization, with a focus area in the center and a context area around the rim. The prior art technique results in a view best utilized when the circular view of the tree can be presented effectively within the form factor of the display being used. However, when the display being used allows a narrow rectangle for display of the tree, the circular view of the unit disc must be distorted as shown in FIG. 1, to make best use of the space in the display area. When the unit disc is distorted, more space is allocated arbitrarily to nodes along the long axis of the ellipse, and the quality of the visualization suffers.